// 常数时间插入、删除和获取随机元素
// Created by madison on 2022/11/6.
//


#include "vector"
#include "unordered_map"

using namespace std;

class RandomizedSet {
public:
    // 方法一：变长数组 + 哈希表
    RandomizedSet() {
        srand((unsigned) time(nullptr));
    }

    bool insert(int val) {
        if (indices.count(val)) {
            return false;
        }
        int index = nums.size();
        nums.emplace_back(val);
        indices[val] = index;
        return true;
    }

    bool remove(int val) {
        if (!indices.count(val)) {
            return false;
        }
        int index = indices[val];
        int last = nums.back();
        nums[index] = indices[val];
        indices[last] = index;
        nums.pop_back();
        indices.erase(val);
        return true;
    }

    int getRandom() {
        int randomIndex = rand() % nums.size();
        return nums[randomIndex];
    }

private:
    vector<int> nums;
    unordered_map<int, int> indices;
};

/**
 * Your RandomizedSet object will be instantiated and called as such:
 **/
int main() {
    auto *obj = new RandomizedSet();
    bool param_1 = obj->insert(3);
    printf("%d\n", param_1);
    bool param_2 = obj->remove(5);
    printf("%d\n", param_2);
    obj->insert(7);
    obj->insert(9);
    obj->insert(1);
    int param_3 = obj->getRandom();
    printf("%d\n", param_3);
    return 0;
}
